#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 10000005;

int mem[MAX];
int R, S;

int main() {
	for(int i = MAX - 1 ; i > 0 ; i--) {
		long long combo = 1;
		for(int j = 1 ; j <= i ; j++) {
			combo *= (i + 1 - j);
			combo /= j;
			if (combo > MAX) {break;}
			mem[combo] = i;
		}
	}
	
	cin >> R;
	for(int t = 1 ; t <= R ; t++) {
		cin >> S;
		int ans = MAX * 10;
		for(int i = 1 ; i * i <= S ; i++) {
			if ((S % i) == 0) {
				ans = min(ans, mem[i] + mem[S / i]);
			}
		}
		printf("Case #%d: %d\n",t,ans);
	}

	return 0;
}
